package org.example.myleet.p708;

public class Solution {
    public Node insert(Node head, int insertVal) {
        //讨论2中特殊情况：没有节点或只有一个节点
        if (head == null) {
            Node cur = new Node(insertVal);
            cur.next = cur;
            return cur;
        }
        if (head.next == head) {
            head.next = new Node(insertVal);
            head.next.next = head;
            return head;
        }
        //下面进行不大于2次遍历完成插入
        //记录走了多少round，round超过1时就可以知道不能再遍历更多了
        int round = 0;
        Node prev = head;
        Node cur = head;
        while (null != cur.next) {
            prev = cur;
            cur = cur.next;
            if (cur == head) {
                //完成一次遍历
                ++round;
                if (round > 1) {
                    break;
                }
            }
            if ((prev.val <= insertVal && insertVal <= cur.val) || (prev.val > cur.val && (insertVal <= cur.val || insertVal >= prev.val))) {
                //找到插入点的情况：
                //1. prev <= insert <= cur
                //2. prev <= insert > cur
                //3. prev > insert <= cur
                Node insert = new Node(insertVal);
                prev.next = insert;
                insert.next = cur;
                return head;
            }
        }
        //默认补偿，实际应该走不到这里
        Node insert = new Node(insertVal);
        prev.next = insert;
        insert.next = cur;
        return head;
    }
}
